package LeetCode;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/majority-element
 */
public class MajorityElement {
    /**
     * 可以先排序，如果第一个数字等于第n/2+1这个数字，说明第一个就是，否则第n/2+1是
     *
     * @param arr
     */
    public static int solution(int[] arr) {
        Arrays.sort(arr);
        return arr[0] == arr[arr.length / 2] ? arr[0] : arr[arr.length / 2];
    }

    /**
     * 执行用时：18 ms, 在所有 Java 提交中击败了7.12%的用户
     * 内存消耗：43.6 MB, 在所有 Java 提交中击败了86.84%的用户
     *
     * @param arr
     * @return
     */
    public static int solution1(int[] arr) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
                if (map.get(arr[i]) > arr.length / 2) {
                    return arr[i];
                }
            } else {
                map.put(arr[i], 1);
            }
        }
        System.out.println("没有目标数据");
        return arr[0];
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.96%的用户
     * 内存消耗：44.5 MB, 在所有 Java 提交中击败了6.76%的用户
     * 摩尔投票法
     * @param arr
     * @return
     */
    public static int solution2(int[] arr) {
        int candidate = arr[0];
        int vote = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == candidate) {
                vote++;
            } else {
                if (vote == 1) {
                    candidate = arr[i];
                } else {
                    vote--;
                }
            }
        }
        return candidate;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 5, 7, 9, 10, 5, 5, 5, 5, 5};
        solution(arr);
        solution1(arr);
    }
}
